Séminaire Lotharingien de Combinatoire, 78B.62 (2017), 12 pp.
Dominique Guillot, Apoorva
Khare and Bala Rajaratnam
The Critical Exponent: a Novel Graph Invariant
Abstract.
A surprising result of FitzGerald and Horn (1977) shows that
Ao
α := (aijα)
is positive semidefinite (p.s.d.) for
every entrywise nonnegative n x n p.s.d. matrix
A = (aij)
if and only if α is a positive integer or
α >=
n-2. Given a graph G, we consider the refined problem of
characterizing the set HG
of entrywise powers preserving
positivity for matrices with a zero pattern encoded by G. Using
algebraic and combinatorial methods, we study how the geometry of G
influences the set HG. Our treatment provides new and
exciting connections between combinatorics and analysis, and leads us
to introduce and compute a new graph invariant called the
critical exponent.
Received: November 14, 2016.
Accepted: February 17, 2017.
Final version: April 1, 2017.
The following versions are available: